/*
 * @Author: szx
 * @Date: 2022-05-19 13:47:16
 * @LastEditTime: 2022-05-19 13:48:46
 * @Description:
 * @FilePath: \leetcode\200-299\215\215.js
 */
var findKthLargest = function (nums, k) {
    return quickSelect(nums, 0, nums.length - 1, k - 1);
};

const quickSelect = (nums, left, right, index) => {
    const rp = Math.floor(Math.random() * (right - left + 1)) + left;
    swap(nums, rp, right);
    let x = nums[right],
        i = left;
    for (let j = left; j < right; ++j) {
        if (nums[j] >= x) {
            swap(nums, i, j);
            i++;
        }
    }
    swap(nums, i, right);
    if (i === index) {
        return nums[i];
    } else {
        return i < index ? quickSelect(nums, i + 1, right, index) : quickSelect(nums, left, i - 1, index);
    }
};

const swap = (nums, index1, index2) => {
    const temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
};
